1、二叉搜索树的第k大节点
思想：因为是二叉搜索树，所以中序遍历是有序的，但是二叉搜索树中序遍历是递增的，也就是如果按照左根右只能求出第k
小的节点，多以需要右根右

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int count=0;
    int ans=0;
    int _kthLargest(TreeNode* root, int k)
    {
        if(root==nullptr)
            return -1;
        if(root->right)
            _kthLargest(root->right,k);
        if(++count==k)
        {
            ans=root->val;
            return ans;
        }
        if(root->left)
            _kthLargest(root->left,k);
        return ans;
    }
    int kthLargest(TreeNode* root, int k) {
        
        return _kthLargest(root,k);

    }
};

2、不用加减乘除求a+b
思想：不用加减  第一时间应该想到位运算，
第一步：因为2个数相加   也就是每个位都相加， 如果按位加 右3中情况，1、一个为0，一个为1，则为一 第2种：2个都为0，则结果为0，第3种都为1，则结果也为0 ，但是
需要进1.这就有点像^,相同为0，相异为1，于是第一步  将a^b，也就是把a，b中  不等的为加起来了
第二步：得考虑将a、b中相同的位相加后进1，怎么进位呢?其实仔细一想，只有都为1的位相加后才需要进1，于是(a&b)<<1,将a&b得到都是同为1的位，再将这些位都向左移动
一位，也就是进1，
第三步：的注意一下  对于负数  不能进位运算，需要将负数  转化为unsign  int  无符号的整数。
class Solution {
public:
    int add(int a, int b) {
        int c=0; int sum;
        do
        {
            sum=a^b;       //将每位相加

            c=(unsigned int)(a&b)<<1;  都为1的位进1。
            a=sum;
            b=c;
        }while(b!=0);
        
        return a;
    }
};


3、二叉搜索树的祖先节点
思想，因为为二叉搜索树，所以  左子树《根《右子树，
因此只需判断  p，q与根节点的大小相比   即可判断 在左边、右边，左右各一个


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if(p==nullptr)
            return q;
        if(q==nullptr)
            return p;
        if((root->val>=p->val&&root->val<=q->val)||(root->val>=q->val&&root->val<=p->val))
            return root;
        if(root->val>=p->val&&root->val>=q->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        if(root->val<=p->val&&root->val<=q->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }

        return nullptr;
    }
};

4、二叉树的祖先
思想：因为与上题不一样，不再是左边小，右边大了
所以 需要递归找节点
如果一个在左一个在右  则结果为根
如果都是left   则结果为root->lefy
如果都是right   则结果为root->right
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr)
            return nullptr;
        if(p==root||q==root)
            return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left&&right)
            return root;
        if(left)
            return left;
        if(right)
            return right;
        return nullptr;
    }
};


5、字符串翻译成数字，，多少中翻译法
思想：首先num<9   只有1中
9<num<26的 有2中
剩下的数字 只需 将num%100判断 是在什么范围
ifnum%100在[10,25]则有num/10+num/100   因为24   即可表示为 2和4   也可以表示为24
ifnum%100>25 或者num%100<9，则只可以表示一种；
有点像青蛙跳台阶
class Solution {
public:
    int translateNum(int num) {
        if(num<10)
            return 1;
        else if(num<26)
            return 2;
        if(num%100>25||num%100<10)
        {
            return translateNum(num/10);
        }
        else
        {
            return translateNum(num/10)+translateNum(num/100);
        }
    }
};